/*
 * BitLinked.h
 *
 *  Created on: 27/08/2012
 *      Author: marciocs5
 */

#ifndef BITLINKED_H_
#define BITLINKED_H_

#include "BitTools.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/*
 *	Estrutura de dados que é um vetor de bits encadeado(???).
 *
 *	A estrutura representa um conjunto. Os elementos são armazenados
 *	em no vetor vector como um vetor caracteristico.
 *
 *	ant e prox indicam respectivamente a ultima palavra não-nula e a primeira
 *	não-nula posterior a cada palavra. Ou seja, se ant[i] = j então vector[j] !=
 *	0 e vector[j+1]= vector[j+2] = ... = vector[i-1] = 0 e analogamente para
 *	prox.
 *
 * */
template<typename T>
class BitVector {
private:
	T* vector;// vetor de bits
	long vectorsz;// tamanho do vetor
	long logw;// log do tamanho da palavra
	long sizew;// tamanho da palavra
	long mask;
	long n;// numero de bits

protected:
	// determina dentro da palavra qual o deslocamento para o bit i
	long inWordIdx(long i);

	// determina a palavra em que o bit i esta
	long wordIdx(long i);

	// determina dentro da palavra idx, o proximo bit 1 depois de i
	long leastBit(long i, long idx);

	//conta no numero de bits 1 na palavra idx
	long countBit(long idx);

public:
	//construtor
	BitVector(long n);

	//destrutor
	virtual ~BitVector();

	//numero de bits
	virtual long size();

	//tamanho do vetor de bits
	virtual long sizeInWord();

	//coloca um bit no conjunto
	virtual void toSet(long i);

	//retira um bit do conjunto
	virtual void toCompl(long i);

	//coloca todos os bits no conjunto
	virtual void allToSet();

	//retira todos os vertices do conjunto
	virtual void allToCompl();

	//verifica se um vertice esta no conjunto
	virtual bool isInSet(long i);

	//OU
	virtual void logicor(BitVector<T>* v);

	//E
	virtual void logicand(BitVector<T>* v);

	//NÃO
	virtual void logicneg();

	//numero de bits setados no conjunto
	virtual long cardOfset();

	//verifica se o conjunto é vazio
	virtual bool isEmpty();

	//next bit no conjuto segundo sua ordem natural
	virtual long nextSet(long i);

	//for debug
	virtual void show();
};

template<typename T>
BitVector<T>::BitVector(long n){
	this->n = n;
	logw = inline_ceillog(sizeof(T), 1) + 3;
	sizew = sizeof(T);
	mask = (1LL << logw) - 1;
	vectorsz = (n >> logw) + 1;
	vector = new T[vectorsz];
	for(long i = 0; i < vectorsz; i++){
		vector[i] = 0;
	}
}

template<typename T>
BitVector<T>::~BitVector(){
	delete vector;
}

template<typename T>
inline long BitVector<T>::inWordIdx(long i){
	return i & mask;
}

template<typename T>
inline long BitVector<T>::wordIdx(long i){
	return i >> logw;
}

template<>
inline long BitVector<int>::leastBit(long i, long idx){
	return builtinLeast<int>(vector[idx] & posmasksimp[i]);
}

template<>
inline long BitVector<long>::leastBit(long i, long idx){
	return builtinLeast<long>(vector[idx] & posmasklsimp[i]);
}

template<typename T>
inline long BitVector<T>::countBit(long idx){
	return builtinCounter<T>(vector[idx]);
}

template<typename T>
inline long BitVector<T>::size(){
	return n;
}

template<typename T>
inline long BitVector<T>::sizeInWord(){
	return vectorsz;
}

template<typename T>
inline void BitVector<T>::toSet(long i){
	vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
}

template<typename T>
inline void BitVector<T>::toCompl(long i){
	vector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
}

template<typename T>
inline void BitVector<T>::allToSet(){
	memset(vector, 255, vectorsz*sizeof(T));
}

template<typename T>
inline void BitVector<T>::allToCompl(){
	memset(vector, 255, vectorsz*sizeof(T));
}

template<typename T>
inline bool BitVector<T>::isInSet(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) != 0;
}

template<typename T>
inline void BitVector<T>::logicor(BitVector<T>* v){
	T* a = vector;
	T* b = v->vector;
	T* c = a + vectorsz;
	for(; a < c; a++, b++){
		*a |= *b;
	}
}

template<typename T>
inline void BitVector<T>::logicand(BitVector<T>* v){
	T* a = vector;
	T* b = v->vector;
	T* c = a + vectorsz;
	for(; a < c; a++, b++){
		*a &= *b;
	}
}

template<typename T>
inline void BitVector<T>::logicneg(){
	T* a = vector;
	T* c = a + vectorsz;
	for(; a < c; a++){
		*a = ~(*a);
	}
}

template<typename T>
inline long BitVector<T>::cardOfset(){
	long counter = 0;
	T* a = vector;
	T* c = a + vectorsz;
	for(; a < c; a++){
		counter += builtinCounter(*a);
	}
}

template<typename T>
inline bool BitVector<T>::isEmpty(){
	T* a = vector;
	T* c = a + vectorsz;
	for(; a < c; a++){
		if((*a) != 0) return false;
	}
	return true;
}

template<>
inline long BitVector<int>::nextSet(long i){
	long finder = builtinLeast<int>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
	if(finder >= 0)return finder + wordIdx(i) << logw;
	for(long j = wordIdx(i) + 1; j < vectorsz; j++){
		 finder = builtinLeast<int>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
		if(finder >= 0)return finder + wordIdx(i) << logw;
	}
	return n+1;
}

template<>
inline long BitVector<long>::nextSet(long i){
	long finder = builtinLeast<long>(vector[wordIdx(i)] & posmasklsimp[inWordIdx(i)]);
	if(finder >= 0)return finder + wordIdx(i) << logw;
	for(long j = wordIdx(i) + 1; j < vectorsz; j++){
		 finder = builtinLeast<long>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
		if(finder >= 0)return finder + wordIdx(i) << logw;
	}
	return n+1;
}

template<typename T>
inline void BitVector<T>::show(){
	printf("\n Estrutura!\n");
	printf("vetor de base! \n");
	for(long i = 0; i < size(); i++){
		if(isInSet(i))printf("<%lu>", i);
	}
	printf("\n");
}

#endif /* BITLINKED_H_ */
